package 每日一题;

import publicClass.TreeNode;

import java.util.Arrays;

/**
 * 449. 序列化和反序列化二叉搜索树
 * 中等
 * 489
 * 相关企业
 * 序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
 *
 * 设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
 *
 * 编码的字符串应尽可能紧凑。
 *
 *
 *
 * 示例 1：
 *
 * 输入：root = [2,1,3]
 * 输出：[2,1,3]
 * 示例 2：
 *
 * 输入：root = []
 * 输出：[]
 *
 *
 * 提示：
 *
 * 树中节点数范围是 [0, 104]
 * 0 <= Node.val <= 104
 * 题目数据 保证 输入的树是一棵二叉搜索树。
 */
public class T449_序列化和反序列化二叉搜索树 {


    // Encodes a tree to a single string.
    //序列化二叉搜索树 使用 逗号分割每个节点，空节点使用负数表示
    //使用前序遍历 根，左，右  同时将空节点记为负数，这样就可以保证还原
    public static String serialize(TreeNode root) {

//        StringBuilder treeStringBuilder = new StringBuilder();
        //如果节点为null
        if (root == null) {
            return "-1";
        }
        String currentValue = String.valueOf(root.val);
        //将左子树序列化为字符串
        String leftTree = serialize(root.left);
//        将左子树序列化为字符串
        String rightTree = serialize(root.right);
//        返回整个树前序遍历生成的字符串
        return currentValue + "," + leftTree + "," + rightTree;
    }

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {

        //将字符串处理为int数组
        String[] split = data.split(",");
        int[] nodeValueData = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            nodeValueData[i] = Integer.parseInt(split[i]);
        }

        TreeNode root = buildSearchTree(nodeValueData);

        return root;
    }

    //序列化时 使用前序遍历 ，第一个数就是根节点 ，第二个数就是左节点，第一个大于根节点的数就是右节点
    private static TreeNode buildSearchTree(int[] nodeValueData) {

        //重建根节点
        if (nodeValueData[0] == -1) {
            return null;
        }
        TreeNode root = new TreeNode(nodeValueData[0]);


        //左节点的坐标为1 还需要找到右节点的坐标
        int rightNodeIndex = -1;
        for (int i = 2; i < nodeValueData.length; i++) {
            if (nodeValueData[i] > nodeValueData[0]) {
                rightNodeIndex = i;
                break;
            }
        }

        //重建左子树
        //大于2两个节点 才会有左节点
        if (nodeValueData.length >= 2) {
            if (rightNodeIndex == -1) {
                root.left = buildSearchTree(Arrays.copyOfRange(nodeValueData, 1, nodeValueData.length));
            } else {
                root.left = buildSearchTree(Arrays.copyOfRange(nodeValueData, 1, rightNodeIndex));
            }

        } else {
            root.left = null;
        }

        //重建右子树
        //找不到右节点的坐标
        if (rightNodeIndex == -1) {
            root.right = null;
        } else {
            root.right = buildSearchTree(Arrays.copyOfRange(nodeValueData, rightNodeIndex, nodeValueData.length));
        }

        return root;
    }


    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);

        treeNode3.left = treeNode2;
        treeNode3.right = treeNode4;
        treeNode2.left = treeNode1;
        treeNode4.right = treeNode5;

        String serialize = serialize(treeNode3);
        System.out.println(serialize);

        TreeNode deserialize = deserialize(serialize);


    }

}
